package 寒假刷题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 统计最高分的节点数目 {
    long maxScore = 0;
    int cnt = 0;
    int n;
    List<Integer>[] list;
    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        list = new List[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            int p = parents[i];
            if (p!=-1){
                list[p].add(i);
            }
        }
        dfs(0);
        return cnt;
    }
    //返回以node为根节点的树的节点数量
    private int dfs(int node) {
        long score = 1;
        //size = 节点总数 - 以node为根节点的树的节点数量
        int size = n-1;
        for (Integer children : list[node]) {
            int t = dfs(children);
            score*=t;
            size-=t;
        }
        //node不为根节点
        if (node!=0){
            score*=size;
        }
        if (score==maxScore){
            cnt++;
        }
        else if (score>maxScore){
            maxScore = score;
            cnt = 1;
        }
        return n - size;
    }
}
